package ua.mykola.dynamicp;

public class DynamicAppoximateStringMatcher {

	public static void main(String[] args) {
		DynamicAppoximateStringMatcher matcher = new DynamicAppoximateStringMatcher(
				"abcd", "abdc");
		int compareStrings = matcher.compareStrings();
		System.out.println(compareStrings);
		matcher.reconstructPath();
	}

	public void reconstructPath() {
		reconstructPath(s, p, s.length, p.length);
	}

	static final int MATCH = 0;
	static final int INSERT = 1;
	static final int DELETE = 2;

	private static class Cell {
		int cost;
		int parent;
	}

	private final char[] s;
	private final char[] p;
	private int maxlen;
	private Cell[][] m;// dynamic programming table

	public DynamicAppoximateStringMatcher(String string, String pattern) {
		this.s = string.toCharArray();
		this.p = pattern.toCharArray();
		maxlen = string.length() > pattern.length() ? string.length() : pattern
				.length();
		m = new Cell[maxlen + 1][maxlen + 1];

		initMatrix();
	}

	private void initMatrix() {
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[i].length; j++) {
				m[i][j] = new Cell();
			}
		}
	}

	public int compareStrings() {
		return compareStrings(s, p);
	}

	private int compareStrings(char[] s, char[] t) {
		int i = -1, j = -1; /* counters */
		int[] opt = new int[3]; /* cost of the three options */
		for (i = 0; i < maxlen + 1; i++) {
			initRow(i);
			initColumn(i);
		}
		for (i = 1; i < (s.length + 1); i++) {
			for (j = 1; j < (t.length + 1); j++) {
				opt[MATCH] = m[i - 1][j - 1].cost + match(s[i - 1], t[j - 1]);
				opt[INSERT] = m[i][j - 1].cost + indel(t[j - 1]);
				opt[DELETE] = m[i - 1][j].cost + indel(s[i - 1]);
				m[i][j].cost = opt[MATCH];
				m[i][j].parent = MATCH;
				int k;
				for (k = INSERT; k <= DELETE; k++)
					if (opt[k] < m[i][j].cost) {
						m[i][j].cost = opt[k];
						m[i][j].parent = k;
					}
			}
		}
		// goal_cell(s, t, i, j);
		printMatrix();
		return (m[i - 1][j - 1].cost);
	}

	void reconstructPath(char[] s, char[] t, int i, int j) {
		if (m[i][j].parent == -1)
			return;
		if (m[i][j].parent == MATCH) {
			reconstructPath(s, t, i - 1, j - 1);
			matchOut(s, t, i, j);
			return;
		}
		if (m[i][j].parent == INSERT) {
			reconstructPath(s, t, i, j - 1);
			insertOut(t, j);
			return;
		}
		if (m[i][j].parent == DELETE) {
			reconstructPath(s, t, i - 1, j);
			deleteOut(s, i);
			return;
		}
	}

	private void deleteOut(char[] s, int i) {
		System.out.print("D");

	}

	private void insertOut(char[] t, int j) {
		System.out.print("I");

	}

	private void matchOut(char[] s, char[] t, int i, int j) {
		if (s[i - 1] == t[j - 1])
			System.out.print("M");
		else
			System.out.print("S");
	}

	private void printMatrix() {
		printMatrixCosts();
		printMatrixParents();
	}

	private void printMatrixCosts() {
		System.out.println("------costs");
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[i].length; j++) {
				System.out.print(m[i][j].cost + " ");
			}
			System.out.println();
		}
	}

	private void printMatrixParents() {
		System.out.println("------parents");
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[i].length; j++) {
				System.out.print(m[i][j].parent + " ");
			}
			System.out.println();
		}
	}

	private void goal_cell(char[] s, char[] t, int i, int j) {
		// TODO Auto-generated method stub
	}

	private void initColumn(int i) {
		m[i][0].cost = i;
		if (i > 0)
			m[i][0].parent = DELETE;
		else
			m[i][0].parent = -1;

	}

	private void initRow(int i) {
		m[0][i].cost = i;
		if (i > 0)
			m[0][i].parent = INSERT;
		else
			m[0][i].parent = -1;

	}

	private int match(char c, char d) {
		if (c == d)
			return 0;
		else
			return 1;
	}

	private int indel(char c) {
		return 1;
	}

}
